package 题目集.图.最短路;

import java.util.*;

/**
 * https://www.acwing.com/problem/content/description/852/
 */
public class ch01_dij模板 {

    public static long dij(int s, int e, List<int[]>[] nodes) {    /*nodes：每个点能抵达的点，以及他们的距离，*/
        long[] dis = new long[nodes.length];
        Arrays.fill(dis, Long.MAX_VALUE);
        PriorityQueue<long[]> q = new PriorityQueue<>((a, b) -> (int) (a[1] - b[1]));
        /*
            vis可以避免重复遍历，提升常数性能，去掉也不会影响结果。
            因为只有某个点的第一短路和第二短路都比其他点要近才会发生重复遍历。
            举个例子：
            s -> a    2
            s -> a    1
            s -> e    3
        */
        boolean[] vis = new boolean[dis.length];    /*记录已出队的节点*/
        dis[s] = 0;
        q.add(new long[]{s, 0});
        while (!q.isEmpty()) {
            long[] cur = q.poll();
            int u = (int) cur[0];
            long d = cur[1];
            if (u == e) return dis[u];
            if (vis[u]) continue;
            vis[u] = true;
            for (int[] edge : nodes[u]) {
                int v = edge[0];
                int w = edge[1];
                if (d + w < dis[v]) {
                    dis[v] = d + w;
                    q.add(new long[]{v, dis[v]});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<int[]>[] edges = new List[n + 1];
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            edges[u].add(new int[]{v, w});
        }
        long dij = dij(1, n, edges);
        System.out.println(dij);
    }

}


